/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
// 题目转换为：从s中挑选字符去匹配t，求总共的方案数
// 递归：自上而下调用，子问题自下而上解决
// 动态规划：自下而上顺序解决子问题


// 递归
var numDistinct = function(s, t) {
    const sl = s.length, tl = t.length
    // 记忆化数组：用来表示[i, j]已经被计算过无需重复计算
    const arr = new Array(sl)
    for(let i = 0; i < arr.length; i++) {
        arr[i] = new Array(tl).fill(-1)
    }
    const dfs = function(i, j) {
        // j已经选完了
        if(j < 0) {
            return 1
        }
        // s已经选完了
        if(i < 0) {
            return 0
        }
        // 如果已经计算过直接返回
        if(arr[i][j] !== -1) return arr[i][j]
        if(s[i] === t[j]) {
            arr[i][j] =  dfs(i - 1, j - 1) + dfs(i - 1, j)
        } else {
            arr[i][j] = dfs(i - 1, j)
        }
        return arr[i][j]
    }
    return dfs(sl - 1, tl - 1)
};
// console.log(numDistinct("babgbag", "bag"));
// 动态规划
var numDistinct = function(s, t) {
    const sl = s.length, tl = t.length
    const dp = new Array(sl + 1).fill().map(item => {
        return new Array(tl + 1).fill(0)
    })
    for(let i = 0; i < sl + 1; i++) {
        for(let j = 0; j < tl + 1; j++) {
            if(j === 0) { //j为空串
                dp[i][j] = 1
            } else if(i === 0) { // i为空串
                dp[i][j] = 0
            } else {
                if(s[i - 1] === t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                } else {
                    dp[i][j] = dp[i - 1][j]
                }
            }
        }
    }
    return dp[sl][tl]
}
console.log(numDistinct("hdhh", ""));